Slide 4: Linear Structures

Stacks: Last-In, First-Out (LIFO) Structure

A Stack is a linear data structure that follows the LIFO principle: the last element added is the first one to be removed. Think of a stack of plates—you always remove the top one. Stacks are fundamental for managing function calls (the Call Stack) and tracking state in algorithms.

Operation	Description
Push(e)	Adds element `e` to the top of the stack.
Pop()	Removes and returns the element at the top.
Peek()	Returns the top element without removing it.
isEmpty()	Checks if the stack contains any elements.

Application: Validating Balanced Brackets

A critical use of stacks is checking if an expression has balanced delimiters (e.g., {}, [], ()).

When an opening bracket is encountered, we Push it onto the stack.
When a closing bracket is encountered, we Pop the top element and check if it is the corresponding opening bracket.
If the stack is empty at the end, the sequence is balanced.

Stack Complexity

The efficiency of core stack operations is paramount, making them a preferred choice for auxiliary storage.

Operation	Time Complexity (Array/Linked List)
Push	$O(1)$
Pop	$O(1)$
Peek	$O(1)$
Access (i-th element)	$O(N)$

📝 Interactive Quiz

1. Consider the bracket sequence: [({})]. Which sequence correctly represents the elements PUSHED onto the stack, followed by the stack's state just before the final check?

A) PUSH: [, (, {. Final Stack: Empty.
B) PUSH: (, {, ]. Final Stack: [.
C) PUSH: [, (, {. Final Stack: [.
D) PUSH: [, (, (. Final Stack: [, (, {.

2. If the numbers 1, 2, and 3 are pushed onto a stack in that order, what is the sequence of popped elements?

A) 1, 2, 3
B) 3, 2, 1
C) 1, 3, 2
D) 2, 1, 3

3. What is the time complexity of the Peek() operation on a stack implemented with a dynamic array?

A) $O(1)$
B) $O(N)$
C) $O(\log N)$
D) $O(N^2)$

4. Besides bracket validation, which of the following is a classic application of a stack?

A) Maintaining a sorted list of items.
B) Implementing "undo" functionality in a text editor.
C) Searching for an element quickly.
D) Storing key-value pairs.

KEY TIPS

💡 Key Tips

Why $O(1)$ is Crucial

The ability to add and remove elements instantly means that using a stack as auxiliary space $S(N)$ for $N$ operations adds only $O(N)$ total time, making it highly efficient.

Implementation

Stacks can be built with dynamic arrays or linked lists. Arrays are often faster but resizing occasionally takes $O(N)$, though amortized time remains $O(1)$.

Recursion Connection

Recursion inherently uses a stack (the Call Stack) to store the state of active function calls. This helps estimate the auxiliary space $S(N)$ required.